UVa/11590 - Prefix lookup/bruteforce.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x){ stringstream s; s << x; return s.str(); }
  23 template <class T> int toInt(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
  24 template <class T> int Size(const T &x){ return (int)x.size(); }
  25
  26 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  27 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  28 #define D(x) cout << #x " is " << x << endl
  29
  30 typedef unsigned long long Int;
  31 const int BUFSIZE = 128;
  32 char buf[BUFSIZE];
  33
  34 int M;
  35 map<string, Int> ans;
  36
  37 struct node{
  38   node * left, * right;
  39   bool end;
  40   node(bool e) : end(e) {
  41     left = right = NULL;
  42   }
  43 };
  44
  45 void clean(node * n){
  46   if (n == NULL) return;
  47   clean(n->left); clean(n->right);
  48   delete n;
  49 }
  50
  51
  52 Int f(string s, node * n){
  53   Int left = 0, right = 0;
  54   if (n->left != NULL){
  55     left = f(s + "0", n->left);
  56   }
  57   if (n->right != NULL){
  58     right = f(s + "1", n->right);
  59   }
  60   if (n->end){
  61     Int x = ((1ULL) << (M - s.size())) - 1;
  62     if (M == 64 && s.size() == 0){
  63       x = ~(0ULL);
  64     }
  65     ans[s] = x - left - right + 1;
  66     //D(s); D(n->end);
  67     //D(ans[s]);
  68   }
  69   Int ret = 0;
  70   if (n->end){
  71     ret = ans[s];
  72   }
  73   return ret + left + right;
  74 }
  75
  76 int main(){
  77   int n;
  78   while (cin >> n >> M && n && M){
  79     vector<string> prefixes(n+1, "");
  80     For(i, 0, n){
  81       cin >> prefixes[i];
  82       prefixes[i].resize(prefixes[i].size()-1); //delete *
  83     }
  84
  85     map<string, int> ans;
  86     for (int i=0; i<(1<<M); ++i){
  87       string s = "";
  88       for (int k=0; k<M; ++k){
  89         char c = !!(i & (1 << k)) + '0';
  90         s = s + c;
  91       }
  92       int ibest = -1, lenbest = INT_MIN;
  93       for (int j=0; j<prefixes.size(); ++j){
  94         string prefix = prefixes[j];
  95
  96         if (s.find(prefix) == 0){
  97           //cout << s << " starts with " << prefix << endl;
  98           if (lenbest < Size(prefix)){
  99             ibest = j;
 100             lenbest = prefix.size();
 101           }
 102         }
 103       }
 104       ans[prefixes[ibest]]++;
 105
 106     }
 107
 108     int K;
 109     cin >> K;
 110     while (K--){
 111       string q;
 112       cin >> q;
 113       q.resize(q.size()-1);
 114       cout << ans[q] << endl;
 115     }
 116     puts(" ");
 117   }
 118   return 0;
 119 }